package me.algo.array;

import com.google.common.base.Stopwatch;

import java.time.Duration;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.concurrent.TimeUnit;

import static java.time.temporal.ChronoUnit.SECONDS;

/**
 * @author guozheng
 * @date 2024/4/20
 */
public class A6 {

    public static void main(String[] args) {
//        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] nums = Data.DT;
        int k = 5000;
//        Deque<Integer> deque = new LinkedList<>();
//        int[] res = new int[nums.length - k + 1];
//         未形成窗口
//        for(int i = 0; i < k; i++) {
//            while(!deque.isEmpty() && deque.peekLast() < nums[i])
//                deque.removeLast();
//            deque.addLast(nums[i]);
//        }
        System.out.println(nums.length);

        long l = System.currentTimeMillis();
        int[] ints = maxSlidingWindow2(nums, k);
        System.out.println(ints);
        long end = System.currentTimeMillis();
        System.out.println(end - l);
    }

    /**
     * 239. 滑动窗口最大值
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (Objects.isNull(nums) || k < 1 || k > nums.length) {
            return new int[0];
        }
        int[] rtn = new int[nums.length - k + 1];
        PriorityQueue<Integer> periodMaxQue = new PriorityQueue<>(k, (o2, o1) -> {
            if (o1 > o2) {
                return 1;
            } else if (o1.equals(o2)) {
                return 0;
            }
            return -1;
        });
        for (int i = 0; i < nums.length - k+1; i++) {
            if (i == 0) {
                for (int j = 0; j < k; j++) {
                    periodMaxQue.add(nums[j]);
                }
                Integer max = periodMaxQue.peek();
                rtn[i] = max;
            } else {
                int left = nums[i - 1];
                periodMaxQue.remove(left);
                periodMaxQue.add(nums[i + k - 1]);
                Integer peek = periodMaxQue.peek();
                rtn[i] = peek;
            }
        }
        return rtn;
    }


    /**
     *      * 239. 滑动窗口最大值
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (Objects.isNull(nums) || k < 1 || k > nums.length) {
            return new int[0];
        }
        int[] rtn = new int[nums.length - k + 1];
        LinkedList<Integer> periodMaxQue = new LinkedList<>();
        for (int i = 0; i < nums.length - k+1; i++) {
            if (i == 0) {
                for (int j = 0; j < k; j++) {
                    while (!periodMaxQue.isEmpty() && periodMaxQue.peekLast() < nums[j]) {
                        periodMaxQue.removeLast();
                    }
                    periodMaxQue.addLast(nums[j]);
                }
                Integer max = periodMaxQue.peekFirst();
                rtn[i] = max;
            } else {
                int left = nums[i - 1];
                if (periodMaxQue.peekFirst() == left) {
                    periodMaxQue.removeFirst();
                }
                while (!periodMaxQue.isEmpty() && periodMaxQue.peekLast() < nums[i + k - 1]) {
                    periodMaxQue.removeLast();
                }
                periodMaxQue.add(nums[i + k - 1]);
                Integer peek = periodMaxQue.peekFirst();
                rtn[i] = peek;
            }
        }
        return rtn;
    }
}
